#include<bits/stdc++.h>
using namespace std;

// Class T must has operator < (but need not have operator > and ==)
template <class T>
class BST {
private:
	struct node {
		T val;
		int cnt;
		node * lson;
		node * rson;
		node(const T & _val, const int & _cnt, node * _lson, node * _rson) : val(_val), cnt(_cnt), lson(_lson), rson(_rson) {}
	};
	
	// Clear u and the subtree of u.
	void clear(node *& u) {
		if(u == nullptr) return;
		clear(u -> lson);
		clear(u -> rson);
		delete u;
		u = nullptr;
	}
	
	node * root;
	
	// Insert the number val.
	void insert(const T & val, node *& u) {
		if (u == nullptr) {
			u = new node(val, 1, nullptr, nullptr);
			return;
		}
		if (val < u -> val) insert(val, u -> lson);
		else if (u -> val < val) insert(val, u -> rson);
		else ++u -> cnt;
	}
	
	// Iterate the BST, and put all the elements into the vector v.
	void to_vector(vector <T> & v, node * u) {
		if (u == nullptr) return;
		to_vector(v, u -> lson);
		for (int i = 0; i < u -> cnt; ++i) v.push_back(u -> val);
		to_vector(v, u -> rson);
	}
	
public:
	BST(){
		root = nullptr;
	}
	~BST() {
		clear(root);
	}
	void insert(const T & val) {
		insert(val, root);
	}
	void to_vector(vector <T> & data) {
		to_vector(data, root);
	}
};

template <class T>
void BST_sort(vector <T> & data){
	BST <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.to_vector(data);
}

template <class T>
void Randomized_BST_sort(vector <T> & data){
	random_shuffle(data.begin(), data.end());
	BST <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.to_vector(data);
}